package leetcode.binaryTree;

import datastructure.tree.TreeNode;

import java.util.Stack;

/**
 * @Description: https://leetcode.cn/problems/maximum-binary-tree/
 * @Author Ammar
 * @Create 2023/7/11 19:14
 */
public class _654_最大二叉树 {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        if (nums == null || nums.length == 0) return null;
        return findRoot(nums, 0, nums.length);
    }

    private TreeNode findRoot(int[] nums, int sIndex, int eIndex) {

        if (sIndex == eIndex) return null;

        int maxIndex = sIndex;
        for (int i = sIndex + 1; i < eIndex; i++) {
            if (nums[maxIndex] < nums[i]) maxIndex = i;
        }
        TreeNode root = new TreeNode(nums[maxIndex]);
        root.left = findRoot(nums, sIndex, maxIndex);
        root.right = findRoot(nums, maxIndex + 1, eIndex);
        return root;
    }

    // 变种。创建一个数组，使其装着每个元素的父节点的索引
    public int[] parentIndexes(int[] nums) {
        if (nums == null || nums.length == 0) return null;
        /*
         * 1.扫描一遍所有的元素
         * 2.保持栈从栈底到栈顶是单调递减的
         */
        int[] lis = new int[nums.length];
        int[] ris = new int[nums.length];
        Stack<Integer> stack = new Stack<>();
        // 初始化
        for (int i = 0; i < nums.length; i++) {
            ris[i] = -1;
            lis[i] = -1;
        }
        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
                ris[stack.pop()] = i;
            }
            if (!stack.isEmpty()) {
                lis[i] = stack.peek();
            }
            stack.push(i);
        }

        int[] pis = new int[nums.length];
        for (int i = 0; i < pis.length; i++) {
            if (lis[i] == -1 && ris[i] == -1) {
                // i位置的是根节点
                pis[i] = -1;
                continue;
            }

            if (lis[i] == -1) {
                pis[i] = ris[i];
            } else if (ris[i] == -1) {
                pis[i] = lis[i];
            } else if (nums[lis[i]] < nums[ris[i]]) {
                pis[i] = lis[i];
            } else {
                pis[i] = ris[i];
            }
        }
        return pis;
    }
}
